package com.iter.devbox.datastructure;

/**
 * 链式链表-双向链表
 * 
 * @author Jimly
 */
public class Linklist {

	/**第一个结点*/
	private Node first;
	
	/**最后一个结点*/
	private Node last;
	
	/**结点个数*/
	private int nodeCount;
	
	/**默认构造方法*/
	public Linklist() {
	}
	
	/**获取某个指定的结点*/
	public Object get(int i) {
		return node(i).item;
	}
	
	/**获取结点个数*/
	public int size() {
		return nodeCount;
	}
	
	/**添加一个结点*/
	public boolean add(Object object) {
		Node node = last;
        Node newNode = new Node(node, object, null);
        last = newNode;
        if (node == null) {
            first = newNode;
        } else {
        	node.next = newNode;
        }
        nodeCount++;
		return true;
	}
	
	/**删除指定元素*/
	public boolean remove(int i) {
		if (i>0 && i<nodeCount) {
			if (i==nodeCount-1) {
				node(i-1).next = null;
				last = node(i-1);
			} else {
				node(i-1).next = node(i+1);
			}
		} else if (i==0) {
			node(1).prev = null;
			first = node(1);
		} else {
			throw new RuntimeException("越界异常");
		}
		nodeCount--;
		return true;
	}
	
	private Node node(int i) {
		Node node = first;
		for (int index=0; index<i; index++) {
			node = node.next;
		}
		return node;
	}
	
	private static class Node {
		/**指向前一个数据元素的指针*/
		private Node prev;
		/**指向后一个数据元素的指针*/
		private Node next;
		/**数据*/
		private Object item;
		
		public Node(Node prev, Object item, Node next) {
			this.prev = prev;
            this.item = item;
            this.next = next;
        }
	}
	
	/**main方法测试*/
	public static void main(String[] args) {
		Linklist linklist = new Linklist();
		System.out.println("初始化：" + linklist);
		linklist.add("1");
		linklist.add("2");
		linklist.add("3");
		linklist.add("4");
		linklist.add("5");
		System.out.println("第i个元素：" + linklist.get(3));
		
		linklist.remove(4);
		System.out.println(linklist.size());
	}
}